#include <stdio.h>
#include <stdlib.h>
#include "list-ch.h"
#include "graph.h"


//VAN EN .H
#define ERROR_MEMORIA 0
#define ERROR_PARAMETROS 0
#define ARISTA_INEXISTE -1
#define NODO_INEXISTE -2
#define OK 1
#define WEIGHT_INICIAL 0
#define GRAFO_INVALIDO 0

#define TAG_INVALIDO 0
#define TAG_MARCADO 1
#define TAG_DESMARCADO 0
#define TAG_INICIALIZA 0


//typedef listADT graphCDT;

//typedef listADT graphADT;

struct graphCDT
{
	listADT listGraph;
	int (*fnComparison) (void* element1, void* element2);
};

typedef struct nodeADT
{
        elementT element;
        int tag;
        listADT adyacents;
}nodeADT;

typedef struct adyacentADT
{
        nodeADT* node;
        elementEdge value;
        int tag;
        int weight;
}adyacentADT;


/*******************************************************************/
/*                                                                 */
/*                   FUNCIONES    ESTATICAS                        */
/*                                                                 */
/*******************************************************************/

//Funcion que compara con la estructura del nodo los elementos dados
static int
fnComparaNodos(void* node1, void* node2, int (*fn) (void* element1, void* element2))
{
       return fn((void*)(&((nodeADT*)node1)->element),(void*)(&((nodeADT*)node2)->element));
}

static int
fnComparaAdyacentes(void* ady1, void* ady2, int (*fn) (void* element1, void* element2))
{
    int resp;
       
    resp = fn( (void*)(&(((adyacentADT*)ady1)->node)->element) , (void*)(&(((adyacentADT*)ady2)->node)->element) ); 
       
	if (!resp)
	{
		if (((adyacentADT*)ady1)->value < ((adyacentADT*)ady2)->value)
			return -1;
		else if (((adyacentADT*)ady1)->value > ((adyacentADT*)ady2)->value)
			return 1;
		else
			return 0;
	}
	
	return resp;
}

//Libera la lista de adyacentes de un nodo
static void
freeAdyacents(graphADT graph, nodeADT* node)
{
       
	adyacentADT *ady;
	listADT listAdy;

	listAdy=node->adyacents;

	SetBegin(listAdy);

	while((ady=GetDato(listAdy))!=NULL)
		switch(deleteEdge(graph,node->element,ady->node->element, ady->value))
		{
			case ARISTA_INEXISTE:
				//printf("ARISTA_INEXISTE %d-%d\n",node->element,ady->node->element);
				break;
			case NODO_INEXISTE:
				printf("NODO_INEXISTE");
		}


	FreeList(listAdy);
	
}

//Busca un nodo dentro del grafo y devuelve su direccion
static nodeADT*
searchNode(graphADT graph, elementT element)
{
     nodeADT* node;
         
     //Me posiciono sobre el primer nodo del grafo
     SetBegin(graph->listGraph);

     //Busco el elemento en los nodos
     while ((node= GetDato( graph->listGraph )) != NULL && node->element!=element)
	 	 ;
		 
	 //Dejo el puntero a la primera posicion
	 SetBegin(graph->listGraph);
		 
	 return node;
}

//Busca un adyacente dentro del nodo
static adyacentADT*
searchAdyacent(graphADT graph, nodeADT* node, elementT adyacent, elementEdge valueEdge)
{
	adyacentADT *ady,*aux;
	listADT listAdy;
	int found=0;

	aux=NULL;

	listAdy=node->adyacents;

	SetBegin(listAdy);

	while((ady=GetDato(listAdy))!=NULL && !found)
		if (ady->node->element==adyacent)
			if (ady->value==valueEdge)
			{
				aux=ady;
				found=1;
			}

	SetBegin(listAdy);

	return aux;
}

//Devuelve si un nodo es adyacente
static int
isNodeAdyacent(graphADT graph, nodeADT* node, elementT adyacent, elementEdge element)
{
	adyacentADT *ady;
	listADT listAdy;
	int found=0;

	listAdy=node->adyacents;

	SetBegin(listAdy);

	while((ady=GetDato(listAdy))!=NULL && !found)
		if (ady->node->element==adyacent)
			if (ady->value==element)
				found=1;


	SetBegin(listAdy);

	return found;
}

//Setea el contenido del tag del nodo
static int
setTagEdge(graphADT graph, elementT elFrom, elementT elTo, elementEdge valueEdge, int tag)
{
	  adyacentADT *adyTo;
          nodeADT* nodeFrom;              
          
          //Verifico que exista un arista entre ambas nodos
          if (!(edgeExists(graph, elFrom, elTo, valueEdge)))
             return ARISTA_INEXISTE;
          
          //Busco los nodos
          if ((nodeFrom = searchNode(graph,elFrom))==NULL)
             return NODO_INEXISTE;
              
          if ((adyTo = searchAdyacent(graph, nodeFrom, elTo, valueEdge))==NULL)
             return ARISTA_INEXISTE;

	  adyTo->tag=tag;

	  return OK;
}

static int
getTagEdge(graphADT graph, elementT elFrom, elementT elTo, elementEdge valueEdge)
{
	  adyacentADT *adyTo;
          nodeADT* nodeFrom, *nodeTo;              
          
          //Verifico que exista un arista entre ambas nodos
          if (!(edgeExists(graph, elFrom, elTo, valueEdge)))
             return ARISTA_INEXISTE;
          
          //Busco los nodos
          if ((nodeFrom = searchNode(graph,elFrom))==NULL)
             return NODO_INEXISTE;
          
          if ((nodeTo = searchNode(graph,elTo))==NULL)
             return NODO_INEXISTE;
          
	  //busco las aristas
          if ((adyTo = searchAdyacent(graph, nodeFrom, elTo, valueEdge))==NULL)
             return ARISTA_INEXISTE;

	  return adyTo->tag;
}

//Peso

//Setea el peso de la arista
static int
setWeightEdge(graphADT graph, elementT elFrom, elementT elTo, elementEdge valueEdge, int weight)
{
	  adyacentADT *adyTo;
          nodeADT* nodeFrom, *nodeTo;              
          
          //Verifico que exista un arista entre ambas nodos
          if (!(edgeExists(graph, elFrom, elTo, valueEdge)))
             return ARISTA_INEXISTE;
          
          //Busco los nodos
          if ((nodeFrom = searchNode(graph,elFrom))==NULL)
             return NODO_INEXISTE;
          
          if ((nodeTo = searchNode(graph,elTo))==NULL)
             return NODO_INEXISTE;
          
          if ((adyTo = searchAdyacent(graph, nodeFrom, elTo, valueEdge))==NULL)
             return ARISTA_INEXISTE;

	  adyTo->weight=weight;

	  return OK;
}

//Obtiene el peso de la arista
static int
getWeightEdge(graphADT graph, elementT elFrom, elementT elTo, elementEdge valueEdge)
{
	  adyacentADT *adyTo;
          nodeADT* nodeFrom, *nodeTo;              
          
          //Verifico que exista un arista entre ambas nodos
          if (!(edgeExists(graph, elFrom, elTo, valueEdge)))
             return ARISTA_INEXISTE;
          
          //Busco los nodos
          if ((nodeFrom = searchNode(graph,elFrom))==NULL)
             return NODO_INEXISTE;
          
          if ((nodeTo = searchNode(graph,elTo))==NULL)
             return NODO_INEXISTE;
          
	  //busco las aristas
          if ((adyTo = searchAdyacent(graph, nodeFrom, elTo, valueEdge))==NULL)
             return ARISTA_INEXISTE;

	  return adyTo->weight;
}

//Nodos

static int
setTagNode(graphADT graph, elementT element,int tag)
{
	nodeADT* node;
	
	  //Busco los nodos
          if ((node = searchNode(graph,element))==NULL)
             return NODO_INEXISTE;

	  node->tag=tag;

	  return OK;
}

static int
getTagNode(graphADT graph, elementT element)
{
	nodeADT* node;
	
	  //Busco los nodos
          if ((node = searchNode(graph,element))==NULL)
             return NODO_INEXISTE;

	  return node->tag;
}

/*******************************************************************/
/*                                                                 */
/*                   FUNCIONES DE TESTEO                           */
/*                                                                 */
/*******************************************************************/
/*
void
imprimeContenidoNodos(graphADT grafo)
{
	nodeADT* node;
	int i=0;

	SetBegin(grafo->listGraph);

	printf("Elementos: ");
	while((node=GetDato(grafo->listGraph))!=NULL)
		printf("%d ",node->element);
	printf("\n");

	SetBegin(grafo->listGraph);

}

void
imprimeContenidoAdyacentes(graphADT grafo, elementT elemento)
{
	adyacentADT* ady;
	nodeADT* node;
	listADT listAdy;
	int i=0;

	if ((node=searchNode(grafo,elemento))==NULL)
	{
		printf("\nERROR: NODO NO EXISTE");
		return;
	}

	listAdy=node->adyacents;

	SetBegin(listAdy);

	printf("\n%d esta conectado con: ",node->element);
	while((ady=GetDato(listAdy))!=NULL)
		printf("%d ",ady->node->element);
	printf("\n");

	SetBegin(listAdy);

}*/


/*******************************************************************/
/*                                                                 */
/*                   FUNCIONES DEL CONTRATO                        */
/*                                                                 */
/*******************************************************************/

//Validar que el grafo no sea NULL
//validar la funciones de evaluacion
//Aclarar que no se puede multiarista

//Crea el grafo
graphADT
newGraph(int (*fn) (void* element1, void* element2))
{
	graphADT graph;
	
	if ((graph=malloc(sizeof(struct graphCDT)))==NULL)
		return NULL;

	graph->fnComparison=fn;
	graph->listGraph=NewList(fnComparaNodos,fn);
	
    return graph; 
}

void
freeGraph(graphADT graph)
{
         nodeADT* node;
         
         SetBegin(graph->listGraph);
         
         //Recorro todos los nodos y libero sus adyacentes
         while ((node= GetDato( graph->listGraph )) != NULL)
         {
		       deleteNode(graph,node->element);
         }
         
         //Libero los nodos
         FreeList(graph->listGraph);
	 free(graph);
}

//Devuelve si el grafo esta vacio
int
graphIsEmpty(graphADT graph)
{
           return countNodes(graph)==0;
}

//Devuelve si el nodo existe
int
nodeExists(graphADT graph,elementT element)
{
         return searchNode(graph,element)!=NULL;
}

//Se crea el nodo y se guarda el elemento dentro del nodo    
int
addNode(graphADT graph, elementT element)
{
         nodeADT* node;
         
         if (nodeExists(graph, element))
            return OK;
         
         //Creo el espacio para el nodo
         if ((node=malloc(sizeof(nodeADT))) == NULL)
             return ERROR_MEMORIA;
         
         //Inicalizo el nodo
         node->element=element;
         node->tag=TAG_INICIALIZA;
         node->adyacents=NewList(fnComparaAdyacentes,graph->fnComparison);
              
         //Inserto el nodo en la lista
         Insert(graph->listGraph,node);
         
         return OK;
}

//Tengo que buscar el nodo donde se encuentra el elemento y luego borrarlo
int
deleteNode(graphADT graph, elementT element)
{
         nodeADT* node;
         
         //Busco el elemento en los nodos
         node=searchNode(graph, element);
		 
	 if (node==NULL)
	    return NODO_INEXISTE;
         
         //Libero la lista de adyacentes
	 freeAdyacents(graph, node);
	
	 //Borro el nodo de la lista ya que se que existe
	 Delete(graph->listGraph,node);

	 //Libero el nodo en memoria
	 free(node);

         return OK;
}


//Retorna si existe una arista entre ambos nodos
int
edgeExists(graphADT graph, elementT elFrom, elementT elTo, elementEdge element)
{
          nodeADT *nodeFrom, *nodeTo;

	  //Valido que el grafo no este vacio o sea NULL
	  if (graphIsEmpty(graph) || graph==NULL)
		return GRAFO_INVALIDO;

          if ((nodeFrom = searchNode(graph,elFrom))==NULL)
             return NODO_INEXISTE;

          if ((nodeTo = searchNode(graph,elTo))==NULL)
             return NODO_INEXISTE;

          return (isNodeAdyacent(graph,nodeFrom,elTo, element)); 
}


//Agrega una arista entre los nodos
int
addEdge(graphADT graph, elementT elFrom, elementT elTo, elementEdge element)
{
          nodeADT *nodeFrom,*nodeTo;
          adyacentADT *edgeFrom;
          
	  //Si existe la arista no hace falta crearla
	  if (edgeExists(graph,elFrom,elTo, element))
	     return OK;

          //Busco los nodos en el grafo
          if ((nodeFrom = searchNode(graph,elFrom))==NULL)
             return NODO_INEXISTE;
          
          if ((nodeTo = searchNode(graph,elTo))==NULL)
             return NODO_INEXISTE;
          
          //Creo el espacio para el adyacente del From
          if ((edgeFrom=malloc(sizeof(adyacentADT))) == NULL)
             return ERROR_MEMORIA;
          
          //Inicializo las aristas
          edgeFrom->tag=TAG_INICIALIZA;
          edgeFrom->node=nodeTo;
          edgeFrom->weight=WEIGHT_INICIAL;
          edgeFrom->value=element;
          
        
          //Agrego los edges a las listas de adyacentes de las nodos
          //Se tienen que agregar cruzadas ya que se agrega nodeFrom en
          //la lista de adyacentes de nodeTo y viceversa.
          Insert(nodeFrom->adyacents, edgeFrom);
           
          return OK;
}

int
deleteEdge(graphADT graph, elementT elFrom, elementT elTo, elementEdge valueEdge)
{
	nodeADT *nodeFrom;
	adyacentADT *adyFrom, *adyTo;
          
	//Verifico que exista una arista entre ambas nodos
	//Si no existe devuelvo OK ya que no existia
	if (!(edgeExists(graph, elFrom, elTo, valueEdge)))
		return OK;
	  
	//Busco los nodos en el grafo
	if ((nodeFrom = searchNode(graph,elFrom))==NULL)
		return NODO_INEXISTE;
	  
	if ((adyFrom = searchAdyacent(graph, nodeFrom, elTo, valueEdge))==NULL)
		return ARISTA_INEXISTE;
	
	//Borro los elementos y retorno su valor de retorno del delete
	if (!Delete(nodeFrom->adyacents,adyTo))
		return ERROR_MEMORIA;

	//Libero los adyacentes
	free(adyFrom);

	return OK;
}

// -- FUNCIONES DE MARCADO --

//Marca la arista
int
markEdge(graphADT graph, elementT elFrom, elementT elTo, elementEdge valueEdge)
{
          return setTagEdge(graph, elFrom, elTo, valueEdge, TAG_MARCADO);
}

//Desmarca la arista
int
unmarkEdge(graphADT graph, elementT elFrom, elementT elTo, elementEdge valueEdge)
{
          return setTagEdge(graph, elFrom, elTo, valueEdge, TAG_DESMARCADO);
}

//Devulve si la arista esta marcada
int
edgeIsMarked(graphADT graph, elementT elFrom, elementT elTo, elementEdge valueEdge)
{
          return (getTagEdge(graph, elFrom, elTo, valueEdge)==TAG_MARCADO);
}

//Marca el nodo
int
markNode(graphADT graph, elementT element)
{
          return setTagNode(graph,element, TAG_MARCADO);
}

//Desmarca el nodo
int
unmarkNode(graphADT graph, elementT element)
{
          return setTagNode(graph,element, TAG_DESMARCADO);
}

//Devuelve si el nodo esta marcado
int
nodeIsMarked(graphADT graph, elementT element)
{
          return (getTagNode(graph, element)==TAG_MARCADO);
}

//Setea el peso de la arista
int
setWeight(graphADT graph, elementT elFrom, elementT elTo, elementEdge valueEdge, int weight)
{
          return setWeightEdge(graph, elFrom, elTo, valueEdge, weight);
}

//Obtiene el peso de la arista
int
getWeight(graphADT graph, elementT elFrom, elementT elTo, elementEdge valueEdge)
{
          return getWeightEdge(graph,elFrom,elTo, valueEdge);
}

//Funciones Generales


//Obtiene el grado de un nodo
int 
gradeNode(graphADT graph, elementT element)
{
          nodeADT *node;
          
          //Busco el nodo
          if ((node = searchNode(graph,element))==NULL)
             return NODO_INEXISTE;
          
	  //Retorno la cantidad de elementos
          return ListCountElements(node->adyacents);
}


//Cuenta la cantidad de nodos
int
countNodes(graphADT graph)
{
           return ListCountElements(graph->listGraph);
}

//Cuenta la cantidad de aristas totales del grafo
int
countEdges(graphADT graph)
{
	   int cantEdges=0;
	   nodeADT* node;

	  //Valido que el grafo no este vacio o sea NULL
	  if (graphIsEmpty(graph) || graph==NULL)
		return GRAFO_INVALIDO;

	   //Me posiciono sobre el primer nodo
	   SetBegin(graph->listGraph);

	   //Recorro todos los nodos y libero sus adyacentes
           while ((node= GetDato( graph->listGraph )) != NULL)
               cantEdges+=ListCountElements(node->adyacents);
	
	   //Me posiciono sobre el primer nodo
	   SetBegin(graph->listGraph);

	   return cantEdges;
}

// -- FUNCIONES QUE DEVUELVEN MEMORIA ALOCADA --


//Crea un vector con los elementos adyacentes al nodo
//Devuelve NULL si no tiene adyacentes
//ACLARACION: El usuario tiene que liberar el vector luego de su uso
adyacentNode* 
getAdyacents(graphADT graph, elementT element)
{
          nodeADT *node;
          adyacentNode* vec;
          adyacentADT* ady;
          listADT listAdy;
          int index=0;

	  //Valido que el grafo no este vacio o sea NULL
	  if (graphIsEmpty(graph) || graph==NULL)
		return NULL;

	  if (!gradeNode(graph,element))
	  	return NULL;

          //Busco el nodo
          if ((node = searchNode(graph,element))==NULL)
             return NULL;
          
          listAdy=node->adyacents;
          
          //Creo el espacio del vector
          if ((vec=(adyacentNode*)malloc(sizeof(adyacentNode) * ListCountElements(listAdy)))==NULL)
          {
              //ERROR DE MEMORIA
              return NULL;
          }
          
          //Seteo la lista en la primera posicion
          SetBegin(listAdy);
          
          //Busco el elemento en los nodos
          while ((ady= GetDato( listAdy )) != NULL)
          {
          	   
		       vec[index].node = ady->node->element;
		       vec[index++].value = ady->value;
          }
          
          return vec;
}

//Crea un vector con los nodos del grafo
//Devuelve NULL si no tiene nodos
//ACLARACION: El usuario tiene que liberar el vector luego de su uso
elementT* 
getNodes(graphADT graph)
{
          nodeADT *node;
          elementT* vec;
          int index=0;

	  //Valido que el grafo no este vacio o sea NULL
	  if (graphIsEmpty(graph) || graph==NULL)
		return NULL;

          //Creo el espacio del vector
          if ((vec=(elementT*)malloc(sizeof(elementT) * countNodes(graph)))==NULL)
          {
              //ERROR DE MEMORIA
              return NULL;
          }
          
          //Seteo la lista en la primera posicion
          SetBegin(graph->listGraph);
          
          //Busco el elemento en los nodos
          while ((node= GetDato( graph->listGraph )) != NULL)
		       vec[index++]= node->element;
          
          return vec;
}

//Duplica el grafo y devuelve una instancia de si mismo
graphADT
duplicateGraph(graphADT graph)
{
          graphADT dupGraph;
          elementT *vecNodes;
          adyacentNode* vecAdy; 
          int i,j,cNodes;

	  if (graphIsEmpty(graph) || graph==NULL)
		return NULL;

	  //creo el nuevo grafo
	  if((dupGraph=newGraph(graph->fnComparison))==NULL)
		return NULL;

	  //Guardo en el vector los nodos
          vecNodes=getNodes(graph);

	  cNodes=countNodes(graph);
	  //Agrego los nodos al duplicado
	  for (i=0;i<cNodes;i++)
		//Si existio un error en el agregado del nodo, libero el grafo y salgo
		if(!(addNode(dupGraph,vecNodes[i])))
		{
			//Libero el grafo
			freeGraph(dupGraph);
			//Libero la memoria del vector
			free(vecNodes);

			return NULL;
		}

	  //Por cada nodo tengo que agregar los adyacentes
	  //Lo tengo que volver a duplicar ya que no puedo agregar aristas
	  //con nodos inexistentes
	  
	  for (i=0;i<cNodes;i++)
	  {
		//Guado los adyacentes al nodo en el vector
		vecAdy=getAdyacents(graph,vecNodes[i]);

		for(j=0;j<gradeNode(graph,vecNodes[i]);j++)
			//Si existe un error al agregar la arista, libero todo
			if(!(addEdge(dupGraph,vecNodes[i],vecAdy[j].node, 1)))
			{
				//Libero el grafo
				freeGraph(dupGraph);
				//Libero la memoria de los adyacentes
				free(vecAdy);
				//Libero la memoria del vector
				free(vecNodes);

				return NULL;
			}
		
		//Libero la memoria de los adyacentes
		free(vecAdy);
	  }

	  //Libero la memoria de los nodos
	  free(vecNodes);
 
          return dupGraph;
}
